package com.yanceysong.codetop.s71_s80;

import java.util.*;


public class S74_Mid_128_最长连续序列 {
    /**
     * .S74_Mid_128_最长连续序列
     * .<p>
     * .LeetCode题目链接：<a href="https://leetcode.cn/problems/longest-consecutive-sequence/">https://leetcode.cn/problems/longest-consecutive-sequence/</a>
     * .<p>
     * .题目描述：给定一个未排序的整数数组 nums，找出数字连续（按整数值相邻，如 x, x+1, x+2, ...）的最长序列的长度。
     * .序列的元素在原数组中不要求连续（即可以从数组中挑选重新排列后形成连续整数序列）。
     * .要求算法时间复杂度为 O(n)。
     * .<p>
     * .示例：
     * .1) 输入：nums = [100,4,200,1,3,2]  输出：4   解释：最长连续序列是 [1,2,3,4]
     * .2) 输入：nums = [0,3,7,2,5,8,4,6,0,1] 输出：9  解释：最长连续序列是 [0,1,2,3,4,5,6,7,8]
     * .3) 输入：nums = [] 输出：0
     * .4) 输入：nums = [9] 输出：1
     * .<p>
     * .标签：哈希表 / 数组 / 序列 / 模拟 / 设计
     * .<p>
     * .核心思路（O(n)）：利用 HashSet 去重 + "只从序列起点出发" 的思想：
     * .- 把所有元素放入集合，支持 O(1) 查找。
     * .- 遍历每个元素 num，仅当 (num - 1) 不在集合中，说明 num 是某个连续序列的起点；
     * .- 之后不断检查 num+1, num+2 ... 是否存在，并统计当前序列长度。
     * .- 避免了重复从中间元素再次扩展导致的 O(n^2) 问题。
     * .<p>
     * .为什么正确：“起点”判定避免重复计算：
     * .假设一个连续序列是：[a, a+1, ..., a+k]，只有 a 满足 (a-1) 不在集合中；
     * .其他元素 a+i 都有前驱存在，因此不会再次被当作起点扩展，整体扩展总次数与序列长度总和是 O(n)。
     * .<p>
     * .ASCII 图解（以 nums = [100,4,200,1,3,2] 为例）：
     * .Set = {1,2,3,4,100,200}
     * .检查：1 的前驱 0 不在集合 -> 作为起点扩展：1→2→3→4  长度=4
     * .检查：2 的前驱 1 在集合 -> 跳过（不是起点）
     * .检查：3 的前驱 2 在集合 -> 跳过
     * .检查：4 的前驱 3 在集合 -> 跳过
     * .检查：100 的前驱 99 不在集合 -> 起点：只有自身 长度=1
     * .检查：200 的前驱 199 不在集合 -> 起点：只有自身 长度=1
     * .最终最大=4
     * .<p>
     * .复杂度分析：
     * .时间复杂度 O(n)：每个元素被插入 HashSet 一次；扩展序列时每个元素最多被访问一次。
     * .空间复杂度 O(n)：HashSet 存储所有去重后的元素。
     * .<p>
     * .其他解法：
     * .1) 排序 O(n log n)：排序后线性扫描，跳过重复，统计最长连续段。
     * .2) 哈希表“区间合并”法：维护每个连续区间的边界长度（与 LeetCode 题目 594/Union-Find 类似），插入新数时合并相邻区间。
     * .3) 并查集(Union-Find)：不如上述直接方法简洁，且需要额外的映射空间。
     * .<p>
     * .关键洞察：
     * .- "从起点扩展" 是避免重复的核心；
     * .- 去重必不可少；重复元素不应影响连续长度；
     * .- 不要在所有元素上盲目向两个方向扩展，否则会退化成 O(n^2)。
     * .<p>
     * .扩展：如果需要返回具体的最长连续序列元素，可在扩展时记录起始值与长度，最后再生成列表。
     */
    public int longestConsecutive(int[] nums) {
        if (nums == null || nums.length == 0) {
            return 0; // 空数组直接返回 0
        }
        // 使用 HashSet 去重并支持 O(1) 存在性查询
        Set<Integer> allNums = new HashSet<>();
        for (int value : nums) {
            allNums.add(value);
        }
        int longestLength = 0; // 最终答案：最长连续序列长度
        // 遍历集合（已去重），尝试找到连续序列的起点
        for (int num : allNums) {
            // 只有当 num-1 不存在时，num 才能作为某连续序列的"起点"
            if (!allNums.contains(num - 1)) {
                int currentVal = num;       // 当前扩展到的值
                int currentLength = 1;      // 当前连续序列长度（至少包含自身）
                // 向上持续扩展 currentVal+1, currentVal+2 ... 直到断裂
                while (allNums.contains(currentVal + 1)) {
                    currentVal += 1;
                    currentLength += 1;
                }
                // 更新答案
                if (currentLength > longestLength) {
                    longestLength = currentLength;
                }
            }
        }
        return longestLength;
    }

    // 备选方案1：排序后线性扫描（O(n log n)），用于对比与正确性校验
    private int longestConsecutiveSort(int[] nums) {
        if (nums == null || nums.length == 0) return 0;
        Arrays.sort(nums); // 排序
        int longest = 1;
        int current = 1;
        for (int i = 1; i < nums.length; i++) {
            if (nums[i] == nums[i - 1]) {
                // 重复元素：不影响当前连续长度，直接跳过
                continue;
            } else if (nums[i] == nums[i - 1] + 1) {
                // 连续 +1
                current++;
            } else {
                // 断裂，重新开始计数
                longest = Math.max(longest, current);
                current = 1;
            }
        }
        longest = Math.max(longest, current);
        return longest;
    }

    // 备选方案2：区间合并法（HashMap 记录每个边界的区间长度）- 时间 O(n)
    // 对于每个新数 x：若 x 不存在
    //   取出左侧区间长度 left = map.getOrDefault(x-1,0)
    //   取出右侧区间长度 right = map.getOrDefault(x+1,0)
    //   新区间总长度 len = left + 1 + right
    //   更新 x 的长度，并更新新区间的两个边界长度(x-left 与 x+right)
    //   维护全局最大值
    public int longestConsecutiveMergeIntervals(int[] nums) {
        Map<Integer, Integer> lengthAt = new HashMap<>(); // 记录该值所在连续区间的长度（仅存储边界 & 中心）
        int max = 0;
        for (int x : nums) {
            if (lengthAt.containsKey(x)) { // 已处理过，跳过
                continue;
            }
            int left = lengthAt.getOrDefault(x - 1, 0);
            int right = lengthAt.getOrDefault(x + 1, 0);
            int merged = left + 1 + right;
            lengthAt.put(x, merged); // 暂存当前位置长度
            // 更新新区间的真实边界长度：x-left (左边界) 与 x+right (右边界)
            if (left > 0) {
                lengthAt.put(x - left, merged);
            } else {
                lengthAt.put(x, merged); // 自己就是左边界
            }
            if (right > 0) {
                lengthAt.put(x + right, merged);
            } else {
                lengthAt.put(x, merged); // 自己也是右边界
            }
            // 为了严谨，强制设置两个边界（无论如何）
            lengthAt.put(x - left, merged);
            lengthAt.put(x + right, merged);
            max = Math.max(max, merged);
        }
        return max;
    }

    // 打印数组工具（测试辅助）
    private static void printArray(int[] arr) {
        System.out.println(Arrays.toString(arr));
    }

    // 随机生成测试数组（含重复）
    private static int[] randomArray(int size, int bound, long seed) {
        Random r = new Random(seed);
        int[] a = new int[size];
        for (int i = 0; i < size; i++) {
            a[i] = r.nextInt(bound * 2) - bound; // 范围 [-bound, bound)
        }
        return a;
    }

    public static void main(String[] args) {
        S74_Mid_128_最长连续序列 solution = new S74_Mid_128_最长连续序列();
        System.out.println("=== 最长连续序列 测试开始 ===\n");

        // 测试1：题目示例1
        int[] case1 = {100, 4, 200, 1, 3, 2};
        runTest("示例1", solution, case1, 4);

        // 测试2：题目示例2
        int[] case2 = {0, 3, 7, 2, 5, 8, 4, 6, 0, 1};
        runTest("示例2", solution, case2, 9);

        // 测试3：空数组
        int[] case3 = {};
        runTest("空数组", solution, case3, 0);

        // 测试4：单元素
        int[] case4 = {9};
        runTest("单元素", solution, case4, 1);

        // 测试5：重复元素与负数混合
        int[] case5 = {0, -1, 1, 2, 2, 3}; // 连续序列 -1,0,1,2,3 长度=5
        runTest("重复元素与负数混合", solution, case5, 5);

        // 测试6：已排序连续序列
        int[] case6 = {5, 6, 7, 8, 9, 10};
        runTest("已排序连续序列", solution, case6, 6);

        // 测试7：无任何连续相邻
        int[] case7 = {10, 20, 30, 40};
        runTest("无连续元素", solution, case7, 1);

        // 测试8：包含长序列与噪音
        int[] case8 = {15, 14, 13, 50, 52, 51, 12, 11, 10, 9, 1000}; // 最长 9..15 -> 7
        runTest("长序列与噪音", solution, case8, 7);

        // 测试9：大范围负数到正数
        int[] case9 = {-3, -2, -1, 0, 1, 2, 4, 6}; // 最长 -3..2 -> 6
        runTest("跨负数正数", solution, case9, 6);

        // 测试10：区间合并算法对比
        int[] case10 = {1, 9, 3, 2, 20, 4, 10, 11, 12}; // 1..4 长度=4, 9..12 长度=4 -> 4
        int expected10 = 4;
        int resMain10 = solution.longestConsecutive(case10);
        int resMerge10 = solution.longestConsecutiveMergeIntervals(case10);
        System.out.println("--- 测试10 区间合并对比 ---");
        printArray(case10);
        System.out.println("主算法结果=" + resMain10 + " 合并法结果=" + resMerge10 + " 期望=" + expected10);
        assert resMain10 == expected10 && resMerge10 == expected10 : "区间合并对比失败";
        System.out.println("✓ 区间合并算法对比通过\n");

        // 测试11：随机数组一致性校验（与排序法比对）
        System.out.println("--- 测试11 随机数组一致性校验 (多组) ---");
        for (int t = 0; t < 5; t++) {
            int[] rnd = randomArray(30, 50, 2025L + t);
            int resMain = solution.longestConsecutive(rnd);
            int resSort = solution.longestConsecutiveSort(rnd);
            if (resMain != resSort) {
                System.out.println("随机用例不一致：");
                printArray(rnd);
                System.out.println("主算法=" + resMain + " 排序算法=" + resSort);
                assert false : "随机一致性失败";
            }
        }
        System.out.println("✓ 随机数组一致性全部通过\n");

        System.out.println("=== 所有测试完成 ===");
    }

    private static void runTest(String title, S74_Mid_128_最长连续序列 solution, int[] input, int expected) {
        System.out.println("--- " + title + " ---");
        printArray(input);
        int result = solution.longestConsecutive(input);
        System.out.println("计算结果=" + result + " 期望=" + expected);
        assert result == expected : title + " 测试未通过";
        System.out.println("✓ 测试通过\n");
    }
}
